#include <unistd.h>
#include <stdlib.h>
#include "my_malloc.h"

/* metadatas struct type definition */
typedef struct s_block *t_block;

struct s_block
{
	/* block size */
	size_t			size;
	/* next and prev block */
	t_block			next, prev;
	/* free block, or not */
	int				free;
	/* point on something */
	void			*ptr;
	/* point on the data */
	char			data[1];
}; 
/* aligne to next 4 multiple */
/**
 *		first version (fonction, basic)
 *				((s-1)/4)*4 +4
 **/
/**
 *		second version (fonction, byte offset)
 *				((s-1)>>2)<<2 + 4
 **/
/**
 * macro version
 **/
#define align4(x) ( ((((x)-1)>>2)<<2) + 4 )
/* size of structure */
#define _HEADSIZE align4(sizeof(struct s_block))


/* /!\ global variable, pointing on the base /!\ */
void                *base = NULL;


/*********************** MALLOC ***********************/
/* find the next free block */
t_block find_block ( t_block *last , size_t size ){
	t_block			b=base;
	/* looking for while b exists, b isn't free and b hasn't size enought */
	while (b && !(b->free && b->size >= align4(size) )) {
		/* save last block */
		*last = b;
		/* go to next block */
		b = b->next;
	}
	return (b);
}

/* extend the heap */
t_block extend_heap ( t_block last , size_t s){
	t_block           b;
	/* b point on the break */
	b = sbrk (0);
	if ( sbrk ( _HEADSIZE + s ) == (void *) -1)
		/* sbrk fails , go to die */
		return (NULL);
	b->size = s;
	b->next = NULL;
	/* attaching to a previous block, if it exists */
	if (last)
	{
		last->next = b;
		b->prev = last;	
	}
	/* set block as used */
	b->free = 0;
	b->ptr = b->data;
	return (b);
}

void split (t_block b, size_t s)
{
	t_block			new;
	void			*tmp;
	tmp = b->data + s;
	new = tmp;
	new->size = b->size - s - _HEADSIZE ;
	new->next = b->next;
	new->prev = b;
	new->free = 1;
	b->next = new;
}

void *my_malloc (size_t s)
{
	t_block			b = NULL;
	t_block			prec = NULL;
	/* faster */
	s = align4(s);
	/* looking for a free block; if base is unset, go to "else" */
	b = find_block(&prec, s);
	if (b)
	{		/* if a free block is found */
		if (b->size > _HEADSIZE+s)
			split (b, s);
		b->size = s;
		b->free = 0;
		b->prev = prec;
	}		
	/* first use, non-initialized base */
	else
	{	/* if base doesn't exist yet */
		if (!base)
			base = sbrk (0);
    	/* extending the heap, else b = NULL */
		if (!(b = extend_heap (prec, s)))
			return NULL;
	}
	return b->data;
}



/*********************** FREE ***********************/
t_block fusion (t_block b){
	if (b->next && b->next->free ){
		b->size += _HEADSIZE + b->next->size;
		b->next = b->next->next;
		if (b->next)
			b->next->prev = b;
	}
	if (b->prev && b->prev->free ){
		b = b->prev;
		b->size += _HEADSIZE + b->next ->size;
		b->next = b->next ->next;
		if (b->next)
			b->next->prev = b;
	}
	return (b);
}



void my_free (void* p)
{
	t_block			b=NULL;
	/* temporary variable */
	char			*temp;
	/* p becomes char* in order to use byte to byte */
	temp = p;
	/* calcutate where's beginning of the struct */
	p = temp - _HEADSIZE;
	/* wtf */
	b = p;
	b = fusion(b);
	b->free = 1;
}

int main () 
{
	void			*debug = NULL;
	int				i=0;
	void			*test[10];
	for (; i<10; i++)
		test[i]=NULL;
	for (i=0; i<4; i++)
	{
		debug = sbrk(0);
		test[i] = my_malloc(sizeof(char));
		debug = sbrk(0);
	}
	my_free (test[0]);
	my_free (test[3]);
	for (i=4; i<10; i++)
    {
        debug = sbrk(0);
        test[i] = my_malloc(sizeof(char));
        debug = sbrk(0);
    }
	for (; i>=0; i--)
	{
	    my_free(test[i]);
		debug = sbrk(0);
	}
		
	return 0;
}

/*		END		*/

